package Algorithm.interview;

/**
 * @Author self
 * @Date 2024/9/7 13:27
 * @Describe 将有序链表转换为二叉搜索树
 */

public class TransBST {
    class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
        }
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) {
            this.val = val;
            left = null;
            right = null;
        }
    }

    public class Solution {
        // 全局变量，指向链表当前的节点
        private ListNode head;

        public TreeNode sortedListToBST(ListNode head) {
            if (head == null) {
                return null;
            }
            // 获取链表的长度
            int size = getLength(head);
            this.head = head; // 初始化全局 head
            // 构造平衡二叉树
            return buildTree(0, size - 1);
        }

        // 获取链表长度的辅助函数
        private int getLength(ListNode head) {
            int length = 0;
            while (head != null) {
                length++;
                head = head.next;
            }
            return length;
        }

        // 构建平衡二叉树的递归函数
        private TreeNode buildTree(int left, int right) {
            if (left > right) {
                return null;
            }

            // 中间节点位置
            int mid = (left + right) / 2;

            // 递归构造左子树
            TreeNode leftChild = buildTree(left, mid - 1);

            // 当前链表节点作为根节点
            TreeNode root = new TreeNode(head.val);

            // 移动链表指针
            head = head.next;

            // 递归构造右子树
            TreeNode rightChild = buildTree(mid + 1, right);

            root.left = leftChild;
            root.right = rightChild;

            return root;
        }
    }

}
